home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / a_utils / _archvrs / unix / unzip51 / match.c < prev    next >
C/C++ Source or Header  |  1992-11-04  |  19KB  |  564 lines
  1. /*---------------------------------------------------------------------------
  2.  
  3.   match.c
  4.  
  5.   The match() routine recursively compares a string to a "pattern" (regular
  6.   expression), returning TRUE if a match is found or FALSE if not.  This
  7.   version is specifically for use with unzip.c:  as did the previous match()
  8.   from SEA, it leaves the case (upper, lower, or mixed) of the string alone,
  9.   but converts any uppercase characters in the pattern to lowercase if indi-
  10.   cated by the global var pInfo->lcflag (which is to say, string is assumed
  11.   to have been converted to lowercase already, if such was necessary).
  12.  
  13.   ---------------------------------------------------------------------------*/
  14.  
  15.  
  16. #ifdef ZIPINFO
  17. #  undef ZIPINFO   /* make certain there is only one version of match.o */
  18. #endif /* ZIPINFO */
  19. #include "unzip.h"
  20.  
  21. static int  matche              __((register char *p, register char *t));
  22. static int  matche_after_star   __((register char *p, register char *t));
  23.  
  24. /* #include "filmatch.h": */
  25. #ifndef BOOLEAN
  26. #  define BOOLEAN short int      /* v1.2 made it short */
  27. #endif
  28.  
  29. /* match defines */
  30. #define MATCH_PATTERN  6    /* bad pattern */
  31. #define MATCH_LITERAL  5    /* match failure on literal match */
  32. #define MATCH_RANGE    4    /* match failure on [..] construct */
  33. #define MATCH_ABORT    3    /* premature end of text string */
  34. #define MATCH_END      2    /* premature end of pattern string */
  35. #define MATCH_VALID    1    /* valid match */
  36.  
  37. /* pattern defines */
  38. #define PATTERN_VALID  0    /* valid pattern */
  39. #define PATTERN_ESC   -1    /* literal escape at end of pattern */
  40. #define PATTERN_RANGE -2    /* malformed range in [..] construct */
  41. #define PATTERN_CLOSE -3    /* no end bracket in [..] construct */
  42. #define PATTERN_EMPTY -4    /* [..] contstruct is empty */
  43.  
  44. /*----------------------------------------------------------------------------
  45. *
  46. *  Match the pattern PATTERN against the string TEXT;
  47. *
  48. *       match() returns TRUE if pattern matches, FALSE otherwise.
  49. *       matche() returns MATCH_VALID if pattern matches, or an errorcode
  50. *           as follows otherwise:
  51. *
  52. *            MATCH_PATTERN  - bad pattern
  53. *            MATCH_RANGE    - match failure on [..] construct
  54. *            MATCH_ABORT    - premature end of text string
  55. *            MATCH_END      - premature end of pattern string
  56. *            MATCH_VALID    - valid match
  57. *
  58. *
  59. *  A match means the entire string TEXT is used up in matching.
  60. *
  61. *  In the pattern string:
  62. *       `*' matches any sequence of characters (zero or more)
  63. *       `?' matches any character
  64. *       [SET] matches any character in the specified set,
  65. *       [!SET] or [^SET] matches any character not in the specified set.
  66. *
  67. *  A set is composed of characters or ranges; a range looks like
  68. *  character hyphen character (as in 0-9 or A-Z).  [0-9a-zA-Z_] is the
  69. *  minimal set of characters allowed in the [..] pattern construct.
  70. *  Other characters are allowed (ie. 8 bit characters) if your system
  71. *  will support them.
  72. *
  73. *  To suppress the special syntactic significance of any of `[]*?!^-\',
  74. *  in a [..] construct and match the character exactly, precede it
  75. *  with a `\'.
  76. *
  77. ----------------------------------------------------------------------------*/
  78.  
  79. /*----------------------------------------------------------------------------
  80. *
  81. *  Match the pattern PATTERN against the string TEXT;
  82. *
  83. *  returns MATCH_VALID if pattern matches, or an errorcode as follows
  84. *  otherwise:
  85. *
  86. *            MATCH_PATTERN  - bad pattern
  87. *            MATCH_RANGE    - match failure on [..] construct
  88. *            MATCH_ABORT    - premature end of text string
  89. *            MATCH_END      - premature end of pattern string
  90. *            MATCH_VALID    - valid match
  91. *
  92. *
  93. *  A match means the entire string TEXT is used up in matching.
  94. *
  95. *  In the pattern string:
  96. *       `*' matches any sequence of characters (zero or more)
  97. *       `?' matches any character
  98. *       [SET] matches any character in the specified set,
  99. *       [!SET] or [^SET] matches any character not in the specified set.
  100. *       \ is allowed within a set to escape a character like ']' or '-'
  101. *
  102. *  A set is composed of characters or ranges; a range looks like
  103. *  character hyphen character (as in 0-9 or A-Z).  [0-9a-zA-Z_] is the
  104. *  minimal set of characters allowed in the [..] pattern construct.
  105. *  Other characters are allowed (ie. 8 bit characters) if your system
  106. *  will support them.
  107. *
  108. *  To suppress the special syntactic significance of any of `[]*?!^-\',
  109. *  within a [..] construct and match the character exactly, precede it
  110. *  with a `\'.
  111. *
  112. ----------------------------------------------------------------------------*/
  113.  
  114. static int matche(p, t)
  115. register char *p;
  116. register char *t;
  117. {
  118.     register char range_start, range_end;  /* start and end in range */
  119.  
  120.     BOOLEAN invert;             /* is this [..] or [!..] */
  121.     BOOLEAN member_match;       /* have I matched the [..] construct? */
  122.     BOOLEAN loop;               /* should I terminate? */
  123.  
  124.     for (;  *p;  p++, t++) {
  125.  
  126.         /* if this is the end of the text then this is the end of the match */
  127.         if (!*t)
  128.             return ((*p == '*') && (*++p == '\0'))?  MATCH_VALID : MATCH_ABORT;
  129.  
  130.         /* determine and react to pattern type */
  131.         switch (*p) {
  132.  
  133.             /* single any character match */
  134.             case '?':
  135.                 break;
  136.  
  137.             /* multiple any character match */
  138.             case '*':
  139.                 return matche_after_star (p, t);
  140.  
  141.             /* [..] construct, single member/exclusion character match */
  142.             case '[': {
  143.  
  144.                 /* move to beginning of range */
  145.                 p++;
  146.  
  147.                 /* check if this is a member match or exclusion match */
  148.                 invert = FALSE;
  149.                 if ((*p == '!') || (*p == '^')) {
  150.                     invert = TRUE;
  151.                     p++;
  152.                 }
  153.  
  154.                 /* if closing bracket here or at range start then we have a
  155.                    malformed pattern */
  156.                 if (*p == ']')
  157.                     return MATCH_PATTERN;
  158.  
  159.                 member_match = FALSE;
  160.                 loop = TRUE;
  161.  
  162.                 while (loop) {
  163.  
  164.                     /* if end of construct then loop is done */
  165.                     if (*p == ']') {
  166.                         loop = FALSE;
  167.                         continue;
  168.                     }
  169.  
  170.                     /* matching a '!', '^', '-', '\' or a ']' */
  171.                     if (*p == '\\')
  172.                         range_start = range_end = *++p;
  173.                     else
  174.                         range_start = range_end = *p;
  175.  
  176.                     /* if end of pattern then bad pattern (Missing ']') */
  177.                     if (!*p)
  178.                         return MATCH_PATTERN;
  179.  
  180.                     /* check for range bar */
  181.                     if (*++p == '-') {
  182.  
  183.                         /* get the range end */
  184.                         range_end = *++p;
  185.  
  186.                         /* if end of pattern or construct then bad pattern */
  187.                         if ((range_end == '\0') || (range_end == ']'))
  188.                             return MATCH_PATTERN;
  189.  
  190.                         /* special character range end */
  191.                         if (range_end == '\\') {
  192.                             range_end = *++p;
  193.  
  194.                             /* if end of text then we have a bad pattern */
  195.                             if (!range_end)
  196.                                 return MATCH_PATTERN;
  197.                         }
  198.  
  199.                         /* move just beyond this range */
  200.                         p++;
  201.                     }
  202.  
  203.                     /* if the text character is in range then match found.
  204.                      * make sure the range letters have the proper
  205.                      * relationship to one another before comparison
  206.                      */
  207.                     if (range_start < range_end) {
  208.                         if ((*t >= range_start) && (*t <= range_end)) {
  209.                             member_match = TRUE;
  210.                             loop = FALSE;
  211.                         }
  212.                     } else {
  213.                         if ((*t >= range_end) && (*t <= range_start)) {
  214.                             member_match = TRUE;
  215.                             loop = FALSE;
  216.                         }
  217.                     }
  218.                 }
  219.  
  220.                 /* if there was a match in an exclusion set then no match */
  221.                 /* if there was no match in a member set then no match */
  222.                 if ((invert && member_match) ||
  223.                    !(invert || member_match))
  224.                     return MATCH_RANGE;
  225.  
  226.                 /* if this is not an exclusion then skip the rest of the [...]
  227.                     construct that already matched. */
  228.                 if (member_match) {
  229.                     while (*p != ']') {
  230.  
  231.                         /* bad pattern (Missing ']') */
  232.                         if (!*p)
  233.                             return MATCH_PATTERN;
  234.  
  235.                         /* skip exact match */
  236.                         if (*p == '\\') {
  237.                             p++;
  238.  
  239.                             /* if end of text then we have a bad pattern */
  240.                             if (!*p)
  241.                                 return MATCH_PATTERN;
  242.                         }
  243.  
  244.                         /* move to next pattern char */
  245.                         p++;
  246.                     }
  247.                 }
  248.  
  249.                 break;
  250.             }  /* switch '[' */
  251.  
  252.             /* must match this character exactly */
  253.             default:
  254. #ifdef OLDSTUFF
  255.                 if (*p != *t)
  256. #else /* !OLDSTUFF */
  257.                 /* do it like arcmatch() (old unzip) did it (v1.2) */
  258.                 if (*t != (char) ((pInfo->lcflag && isupper((int)(*p)))?
  259.                     tolower((int)(*p)) : *p))
  260. #endif /* ?OLDSTUFF */
  261.                     return MATCH_LITERAL;
  262.  
  263.         }  /* switch */
  264.     }  /* for */
  265.  
  266.         /* if end of text not reached then the pattern fails */
  267.     if (*t)
  268.         return MATCH_END;
  269.     else
  270.         return MATCH_VALID;
  271. }
  272.  
  273.  
  274. /*----------------------------------------------------------------------------
  275. *
  276. * recursively call matche() with final segment of PATTERN and of TEXT.
  277. *
  278. ----------------------------------------------------------------------------*/
  279.  
  280. static int matche_after_star (p,t)
  281. register char *p;
  282. register char *t;
  283. {
  284.     register int match = 0;
  285.     register int nextp;
  286.  
  287.     /* pass over existing ? and * in pattern */
  288.     while ((*p == '?') || (*p == '*')) {
  289.  
  290.         /* take one char for each ? and +; if end of text then no match */
  291.         if ((*p == '?') && (!*t++))
  292.                 return MATCH_ABORT;
  293.  
  294.         /* move to next char in pattern */
  295.         p++;
  296.     }
  297.  
  298.     /* if end of pattern we have matched regardless of text left */
  299.     if (!*p)
  300.         return MATCH_VALID;
  301.  
  302.     /* get the next character to match which must be a literal or '[' */
  303.     nextp = *p;
  304.  
  305.     /* Continue until we run out of text or definite result seen */
  306.     do {
  307.         /* a precondition for matching is that the next character
  308.          * in the pattern match the next character in the text or that
  309.          * the next pattern char is the beginning of a range.  Increment
  310.          * text pointer as we go here.
  311.          */
  312.         if ((nextp == *t) || (nextp == '['))
  313.             match = matche(p, t);
  314.  
  315.         /* if the end of text is reached then no match */
  316.         if (!*t++)
  317.             match = MATCH_ABORT;
  318.  
  319.     } while ((match != MATCH_VALID) &&
  320.              (match != MATCH_ABORT) &&
  321.              (match != MATCH_PATTERN));
  322.  
  323.     /* return result */
  324.     return match;
  325. }
  326.  
  327.  
  328. /*----------------------------------------------------------------------------
  329. *
  330. * match() is a shell to matche() to return only BOOLEAN values.
  331. *
  332. ----------------------------------------------------------------------------*/
  333.  
  334. int match(string,pattern)
  335. char *string;
  336. char *pattern;
  337. {
  338.     int error_type;
  339.     error_type = matche(pattern,string);
  340.     return (error_type == MATCH_VALID ) ? TRUE : FALSE;
  341. }
  342.  
  343.  
  344. #ifdef TEST_MATCH
  345.  
  346. /*----------------------------------------------------------------------------
  347. *
  348. * Return TRUE if PATTERN has any special wildcard characters
  349. *
  350. ----------------------------------------------------------------------------*/
  351.  
  352. BOOLEAN is_pattern (char *pattern);
  353.  
  354. /*----------------------------------------------------------------------------
  355. *
  356. * Return TRUE if PATTERN has is a well formed regular expression according
  357. * to the above syntax
  358. *
  359. * error_type is a return code based on the type of pattern error.  Zero is
  360. * returned in error_type if the pattern is a valid one.  error_type return
  361. * values are as follows:
  362. *
  363. *   PATTERN_VALID - pattern is well formed
  364. *   PATTERN_RANGE - [..] construct has a no end range in a '-' pair (ie [a-])
  365. *   PATTERN_CLOSE - [..] construct has no end bracket (ie [abc-g )
  366. *   PATTERN_EMPTY - [..] construct is empty (ie [])
  367. *
  368. ----------------------------------------------------------------------------*/
  369.  
  370. BOOLEAN is_valid_pattern (char *pattern, int *error_type);
  371. int fast_match_after_star (register char *pattern, register char *text);
  372.  
  373. /*----------------------------------------------------------------------------
  374. *
  375. * Return TRUE if PATTERN has any special wildcard characters
  376. *
  377. ----------------------------------------------------------------------------*/
  378.  
  379. BOOLEAN is_pattern (char *p)
  380. {
  381.     while (*p)
  382.         switch (*p++) {
  383.             case '?':
  384.             case '*':
  385.             case '[':
  386.                 return TRUE;
  387.         }
  388.     return FALSE;
  389. }
  390.  
  391.  
  392. /*----------------------------------------------------------------------------
  393. *
  394. * Return TRUE if PATTERN has is a well formed regular expression according
  395. * to the above syntax
  396. *
  397. * error_type is a return code based on the type of pattern error.  Zero is
  398. * returned in error_type if the pattern is a valid one.  error_type return
  399. * values are as follows:
  400. *
  401. *   PATTERN_VALID - pattern is well formed
  402. *   PATTERN_RANGE - [..] construct has a no end range in a '-' pair (ie [a-])
  403. *   PATTERN_CLOSE - [..] construct has no end bracket (ie [abc-g )
  404. *   PATTERN_EMPTY - [..] construct is empty (ie [])
  405. *
  406. ----------------------------------------------------------------------------*/
  407.  
  408. BOOLEAN is_valid_pattern (char *p, int *error_type)
  409. {
  410.     /* init error_type */
  411.     *error_type = PATTERN_VALID;
  412.  
  413.     /* loop through pattern to EOS */
  414.     while (*p) {
  415.  
  416.         /* determine pattern type */
  417.         switch (*p) {
  418.  
  419.             /* the [..] construct must be well formed */
  420.             case '[':
  421.                 p++;
  422.  
  423.                 /* if the next character is ']' then bad pattern */
  424.                 if (*p == ']') {
  425.                     *error_type = PATTERN_EMPTY;
  426.                     return FALSE;
  427.                 }
  428.  
  429.                 /* if end of pattern here then bad pattern */
  430.                 if (!*p) {
  431.                     *error_type = PATTERN_CLOSE;
  432.                     return FALSE;
  433.                 }
  434.  
  435.                 /* loop to end of [..] construct */
  436.                 while (*p != ']') {
  437.  
  438.                     /* check for literal escape */
  439.                     if (*p == '\\') {
  440.                         p++;
  441.  
  442.                         /* if end of pattern here then bad pattern */
  443.                         if (!*p++) {
  444.                             *error_type = PATTERN_ESC;
  445.                             return FALSE;
  446.                         }
  447.                     } else
  448.                         p++;
  449.  
  450.                     /* if end of pattern here then bad pattern */
  451.                     if (!*p) {
  452.                         *error_type = PATTERN_CLOSE;
  453.                         return FALSE;
  454.                     }
  455.  
  456.                     /* if this a range */
  457.                     if (*p == '-') {
  458.  
  459.                         /* we must have an end of range */
  460.                         if (!*++p || (*p == ']')) {
  461.                             *error_type = PATTERN_RANGE;
  462.                             return FALSE;
  463.                         } else {
  464.  
  465.                             /* check for literal escape */
  466.                             if (*p == '\\')
  467.                                 p++;
  468.  
  469.                             /* if end of pattern here then bad pattern */
  470.                             if (!*p++) {
  471.                                 *error_type = PATTERN_ESC;
  472.                                 return FALSE;
  473.                             }
  474.                         }
  475.                     }
  476.                 }
  477.                 break;
  478.  
  479.             /* all other characters are valid pattern elements */
  480.             case '*':
  481.             case '?':
  482.             default:
  483.                 p++;                /* "normal" character */
  484.                 break;
  485.         }    /* switch */
  486.     }
  487.  
  488.     return TRUE;
  489. }
  490.  
  491.  
  492.     /*
  493.     * This test main expects as first arg the pattern and as second arg
  494.     * the match string.  Output is yay or nay on match.  If nay on
  495.     * match then the error code is parsed and written.
  496.     */
  497.  
  498. #include <stdio.h>
  499.  
  500. int main(int argc, char *argv[])
  501. {
  502.     int error;
  503.     int is_valid_error;
  504.  
  505.     if (argc != 3)
  506.         printf("Usage:  MATCH Pattern Text\n");
  507.     else {
  508.         printf("Pattern: %s\n", argv[1]);
  509.         printf("Text   : %s\n", argv[2]);
  510.  
  511.         if (!is_pattern(argv[1]))
  512.             printf("    First Argument Is Not A Pattern\n");
  513.         else {
  514.             match(argv[1],argv[2]) ? printf("TRUE") : printf("FALSE");
  515.             error = matche(argv[1],argv[2]);
  516.             is_valid_pattern(argv[1],&is_valid_error);
  517.  
  518.             switch (error) {
  519.                 case MATCH_VALID:
  520.                     printf("    Match Successful");
  521.                     if (is_valid_error != PATTERN_VALID)
  522.                         printf(" -- is_valid_pattern() is complaining\n");
  523.                     else
  524.                         printf("\n");
  525.                     break;
  526.                 case MATCH_RANGE:
  527.                     printf("    Match Failed on [..]\n");
  528.                     break;
  529.                 case MATCH_ABORT:
  530.                     printf("    Match Failed on Early Text Termination\n");
  531.                     break;
  532.                 case MATCH_END:
  533.                     printf("    Match Failed on Early Pattern Termination\n");
  534.                     break;
  535.                 case MATCH_PATTERN:
  536.                     switch (is_valid_error) {
  537.                         case PATTERN_VALID:
  538.                             printf("    Internal Disagreement On Pattern\n");
  539.                             break;
  540.                         case PATTERN_RANGE:
  541.                             printf("    No End of Range in [..] Construct\n");
  542.                             break;
  543.                         case PATTERN_CLOSE:
  544.                             printf("    [..] Construct is Open\n");
  545.                             break;
  546.                         case PATTERN_EMPTY:
  547.                             printf("    [..] Construct is Empty\n");
  548.                             break;
  549.                         default:
  550.                             printf("    Internal Error in is_valid_pattern()\n");
  551.                     }
  552.                     break;
  553.                 default:
  554.                     printf("    Internal Error in matche()\n");
  555.                     break;
  556.             } /* switch */
  557.         }
  558.  
  559.     }
  560.     return(0);
  561. }
  562.  
  563. #endif  /* TEST_MATCH */
  564.